package me.mingshan.leetcode;

/**
 * 148. 排序链表
 * <p>
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 * 进阶：
 * <p>
 * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class L_148_SortList {

    public static void main(String[] args) {
        ListNode next4 = new ListNode(0, null);
        ListNode next3 = new ListNode(4, next4);
        ListNode next2 = new ListNode(3, next3);
        ListNode next1 = new ListNode(5, next2);
        ListNode head = new ListNode(-1, next1);

        System.out.println(sortList4(head));
    }

    /**
     * 思路：
     * <p>
     * 可以使用插入排序，时间复杂度为O(N^2)
     *
     * @param head
     * @return
     */
    public static ListNode sortList1(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;

        int i = 0;
        while (curr != null) {
            ListNode next = curr.next;

            // 如果当前元素大于前一个元素，那么说明现在的排序是正确的，不需要进行排序
            // 否则，将当前元素插入到已排序的数组中
            if (prev != null && prev.val > curr.val) {
                ListNode newHead = inertSort(curr, prev, head, i);
                if (newHead != head) {
                    head = newHead;
                }
            } else {
                // 如果当前元素已插入到前面排序的链表中，则prev不再更新，原因是prev已指向curr的下一个元素，无需更新
                // 如果当前元素无需更新，那么正常向后走
                prev = curr;
            }

            curr = next;
            i++;
        }

        return head;
    }

    private static ListNode inertSort(ListNode waitInsert, ListNode waitInsertPrev, ListNode head, int i) {
        if (waitInsert == head) {
            return head;
        }

        int j = 0;
        ListNode curr = head;
        ListNode prev = null;

        while (curr != null) {
            // 遍历到当前元素时，停止遍历
            if (j == i) {
                break;
            }

            // 如果待插入的元素小于等于当前元素，则插入到当前元素前面
            ListNode next = curr.next;
            if (waitInsert.val <= curr.val) {
                // 断掉原先的节点
                if (waitInsertPrev != null) {
                    waitInsertPrev.next = waitInsert.next;
                }

                if (curr == head) {
                    head = waitInsert;
                    waitInsert.next = curr;
                } else {
                    // 上一个节点next指向新的节点
                    prev.next = waitInsert;
                    // 新节点next指向原先的节点
                    waitInsert.next = curr;
                }
                return head;
            }

            prev = curr;
            curr = next;
        }

        return head;
    }

    /**
     * 进阶：使用O(nlogn) 时间复杂度，空间复杂度O(1)
     * <p>
     * 符合的排序算法：
     * 1. 快排
     * 2. 归并排序
     * <p>
     * 快排的思想是分治：
     * 选择一个基准元素，将数组分为两部分，小于基准元素的放在左边，大于基准元素的放在右边
     * 然后再针对两个子数组进行递归排序，直至所有元素都排序完成
     * <p>
     * 归并排序的思想是分治：
     * 将数组分为两部分，分别进行排序，然后合并两个排序的数组
     * <p>
     * 从递归和快排的算法思想来看，归并排序更适合链表排序，因为快排要从后往前找，单链表无法实现
     * <p>
     * 所以这里可以使用归并排序
     * <p>
     * 1. 找到链表的中间节点，将链表分成两个
     * 2. 递归对两个子数组进行排序
     * 3. 合并两个排序的数组
     *
     * @param head
     * @return
     */
    public static ListNode sortList3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        // 快慢指针
        // 快指针每次走两步，慢指针每次走一步
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode midNode = slow.next;
        slow.next = null;

        ListNode left = sortList3(midNode);
        ListNode right = sortList3(head);

        return merge(left, right);
    }

    /**
     * 合并两个已排序链表
     *
     * @param midNode
     * @param head
     * @return
     */
    private static ListNode merge(ListNode midNode, ListNode head) {
        if (midNode == null || head == null) {
            return midNode == null ? head : midNode;
        }

        ListNode dummyNode = new ListNode(0);

        ListNode curr1 = head;
        ListNode curr2 = midNode;

        ListNode newCurr = dummyNode;

        while (curr1 != null && curr2 != null) {
            if (curr1.val < curr2.val) {
                ListNode next = curr1.next;
                curr1.next = null;

                newCurr.next = curr1;
                newCurr = newCurr.next;
                curr1 = next;
            } else {
                ListNode next = curr2.next;
                curr2.next = null;

                newCurr.next = curr2;
                newCurr = newCurr.next;
                curr2 = next;
            }
        }

        if (curr1 != null) {
            newCurr.next = curr1;
        }
        if (curr2 != null) {
            newCurr.next = curr2;
        }

        return dummyNode.next;
    }

    /**
     * 进阶：使用O(nlogn) 时间复杂度，空间复杂度O(1)
     * <p>
     * 如果要把空间复杂度降为O(1)，那么归并排序就不使用递归，可以使用自底向上的 方法
     * <p>
     * 思想：
     * <p>
     * 1. 先将链表分为多个子数组，初始每个子数组的长度为1，然后每两个子数组进行合并，直到所有子数组都排序完毕
     * 2. 然后将每个子数组的长度翻倍，重复步骤1，直到所有子数组的长度都等于链表的长度
     *
     * 困难点:
     * 1. 需要在遍历链表的时候，就需要定位两组相邻的链表（两个分组需要与原链表断开）并进行合并，合并后需要与原链表重新连接
     * 2. 需要处理很多边界问题，比如1. 头节点变更，2.中间的分组断开与重新连接，3.处理最后一个分组为空的情况
     *
     * @param head
     * @return
     */
    public static ListNode sortList4(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        // 步长，用来确定每组链表的长度
        for (int step = 1; step < length; step *= 2) {
            boolean first = false;
            // 紧挨的两组链表进行归并
            ListNode group1Head = null;
            ListNode group1Curr = null;
            ListNode group1HeadPrev = null;

            ListNode group2Head = null;
            ListNode group2Curr = null;

            // 按照步长，获取组1和组2的头结点, 并将组1和组2的与原链表断开
            // 然后合并两个有序链表，形成一个新链表，最后将新链表与后续的链表连接起来

            int currStep = 0;

            curr = head;
            ListNode prev = null;
            int count = 0;
            while (curr != null) {
                currStep++;
                count++;
                ListNode next = curr.next;

                if (currStep <= step) {
                    if (group1Head == null) {
                        group1Head = curr;
                        group1Curr = curr;
                        group1HeadPrev = prev;
                    } else {
                        group1Curr = curr;
                    }

                    if (currStep == step) {
                        // 断开g1的链接
                        // 断开g1前面的连接
                        if (group1HeadPrev != null) {
                            group1HeadPrev.next = null;
                        }
                        // 断开g1后面的链接
                        group1Curr.next = null;
                    }
                }

                if (currStep > step) {
                    if (group2Head == null) {
                        group2Head = curr;
                        group2Curr = curr;
                    } else {
                        group2Curr = curr;
                    }
                }

                // 当前两个组已经定位完毕（1. 两个数组都有 2. 已到达链表末尾，无g2）
                // 处理两个组
                if (currStep == 2 * step || count == length) {
                    if (group2Head == null) {
                        // 直接连接g1 尾部
                        // g1的上一个节点，与新的链表重新连接
                        if (group1HeadPrev != null) {
                            group1HeadPrev.next = group1Head;
                        }
                    } else {
                        // 断开g2 后面连接
                        ListNode nextHead = group2Curr.next;
                        group2Curr.next = null;

                        // 合并两个有序链表
                        ListNode newHead = merge2(group1Head, group2Head);
                        // 更新头节点
                        if (!first) {
                            head = newHead;
                            first = true;
                        }

                        // 获取链表的尾节点，与剩余的链表重新连接
                        ListNode currTemp = newHead;
                        ListNode tail = null;
                        while (currTemp != null) {
                            tail = currTemp;
                            currTemp = currTemp.next;
                        }
                        tail.next = nextHead;

                        // g1的上一个节点，与新的链表重新连接
                        if (group1HeadPrev != null) {
                            group1HeadPrev.next = newHead;
                        }

                        // 这里需要知道当前位置，因为curr已经被交换，所以不能直接用prev = curr;
                        // 合并之后的尾节点
                        prev = tail;
                    }

                    // 重置
                    currStep = 0;
                    group1Curr = null;
                    group1Head = null;
                    group1HeadPrev = null;

                    group2Head = null;
                    group2Curr = null;
                } else {
                    prev = curr;
                }

                curr = next;
            }

        }

        return head;
    }

    /**
     * 合并两个已排序链表, 返回新的头节点
     *
     * @param midNode
     * @param head
     * @return
     */
    private static ListNode merge2(ListNode midNode, ListNode head) {
        if (midNode == null || head == null) {
            return midNode == null ? head : midNode;
        }

        ListNode dummyNode = new ListNode(0);

        ListNode curr1 = head;
        ListNode curr2 = midNode;

        ListNode newCurr = dummyNode;

        while (curr1 != null && curr2 != null) {
            if (curr1.val < curr2.val) {
                ListNode next = curr1.next;
                curr1.next = null;

                newCurr.next = curr1;
                newCurr = newCurr.next;
                curr1 = next;
            } else {
                ListNode next = curr2.next;
                curr2.next = null;

                newCurr.next = curr2;
                newCurr = newCurr.next;
                curr2 = next;
            }
        }

        if (curr1 != null) {
            newCurr.next = curr1;
        }
        if (curr2 != null) {
            newCurr.next = curr2;
        }

        // 返回新链表尾节点
        ListNode newHead = dummyNode.next;
        dummyNode.next = null;
        return newHead;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
